"""
假设你是一位顺风车司机，车上最初有capacity个空座位可以用来载客。由于道路的限制，
车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表trips[][]，
其中trips[i] = [num_passengers, start_location, end_location]包含了第 i 组乘客的行程信息：
必须接送的乘客数量；
乘客的上车地点；
以及乘客的下车地点。
这些给出的地点位置是从你的初始出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务
（当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回 false）。

示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

示例 3：
输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true

示例 4：
输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

链接：https://leetcode-cn.com/problems/car-pooling
"""
from mode import *


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        """
        1.首先按照上车地点距离初始位置距离排序；初始化小顶堆，小顶堆用来记录接下来最早需要下车的乘客人数。
        2.顺序遍历 trips，首先更新当前车的位置距离起点的距离 dist，主要是为了解决 “先下后上” 的情况，
            假如当前乘客已满，但是当前距离与小顶堆堆顶元素比较发现有乘客需要下车，
            此处一个循环是为了解决在上次还未到下车距离此时又超过了下车位置的乘客一并全部下车的情况，
            循环直至没有乘客需要下车位置，再将这一站要上车的乘客加进来。
        3.如果此时乘客人数大于车容量，那么就无法完成任务。
        4.如果可以继续，则将这一站乘客需要下车的距离及人数加入到小顶堆中；继续遍历 trips。
        5.参考评论区：直接将下车位置及人数和上车位置及人数放在一个列表中进行排序，然后顺序遍历，在特定的位置上下车，判断是否小于车容量，很巧妙。
        """
        trips.sort(key=lambda x: x[1])
        print(trips)
        offDist = []
        count = 0
        for i in range(len(trips)):
            dist = trips[i][1]
            while offDist and dist >= offDist[0][0]:
                _, passenger = heapq.heappop(offDist)
                count -= passenger
            count += trips[i][0]
            if count > capacity:
                return False
            heapq.heappush(offDist, [trips[i][-1], trips[i][0]])
        return True


if __name__ == "__main__":
    A = Solution()
    print(A.carPooling([[2, 1, 5], [3, 3, 7]], 5))

